package Math;//给你一个数组 points ，其中 points[i] = [xi, yi] 表示 X-Y 平面上的一个点。求最多有多少个点在同一条直线上。
//
// 
//
// 示例 1： 
//
// 
//输入：points = [[1,1],[2,2],[3,3]]
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
//输出：4
// 
//
// 
//
// 提示： 
//
// 
// 1 <= points.length <= 300 
// points[i].length == 2 
// -10⁴ <= xi, yi <= 10⁴ 
// points 中的所有点 互不相同 
// 
// Related Topics 几何 数组 哈希表 数学 👍 403 👎 0


import java.util.HashMap;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class maxPoints {
    public static int maxPoints(int[][] points) {
        /**
         遍历数组中的所有点的位置，两两计算斜率
         假设我们当前枚举到点 i，如果直线同时经过另外两个不同的点 j 和 k，
         么可以发现点 i 和点 j 所连直线的斜率恰等于点 i和点 k所连直线的斜率。于是我们可以统计其他所有点与点 i 所连直线的斜率，
         出现次数最多的斜率即为经过点数最多的直线的斜率，其经过的点数为该斜率出现的次数加一（点 i 自身也要被统计）。
         */
        /**
         * 如何记录斜率
         *
         *
         *
         * */
        int n = points.length;
        int ans = 1;  //初始为1，肯定有1个点
        for (int i = 0; i < n; i++) {
            Map<String, Integer> map = new HashMap<>();
            // 由当前点 i 发出的直线所经过的最多点数量
            int max = 0;
            for (int j = i + 1; j < n; j++) {
                int x1 = points[i][0], y1 = points[i][1], x2 = points[j][0], y2 = points[j][1];
                //a为横坐标差，b为纵坐标差
                int a = x1 - x2, b = y1 - y2;
                int k = gcd(a, b);
                String key = (a / k) + "_" + (b / k);
                map.put(key, map.getOrDefault(key, 0) + 1);
                max = Math.max(max, map.get(key));
            }
            ans = Math.max(ans, max + 1);
        }
        return ans;
    }

    public static int maxPoints1(int[][] points) {
        int len = points.length;
        //当只有两个点时，肯定能构成直线
        if(len == 2){
            return 1;
        }
        int max = 0;
        for (int i = 0; i < len; i++) {
            //每次固定一个点，取和其他点进行计算
            int x1 = points[i][0], y1 = points[i][1];
            HashMap<String, Integer> map = new HashMap<>(); //计数
            for (int j = i+1; j < len; j++) {
                int x2 = points[j][0], y2 = points[j][1];
                StringBuilder sb = new StringBuilder();
                /**
                 * 固定一个点，遍历剩余的点，利用 ax+by+c=0中 的a,b,c唯一表示一条直线
                 * 若(a,b,c)在哈希表中重复，则相应的在直线上的点数目加1.
                 * */
                if(x1 == x2){
                    sb.append("1_");    // a
                    sb.append("0_");    // b
                    sb.append(-x1);     // c
                }else if(y1 == y2){
                    sb.append("0_");     // a
                    sb.append("1_");     // b
                    sb.append(-y1);      // c
                }else{
                    sb.append(1.0);      // a
                    sb.append(1.0 * (x1 - x2) / (y2 - y1));    // b
                    sb.append(1.0 * (x1 * y2 - x2 * y1) / (y1 - y2));    // c
                }
                String key = sb.toString();
                if(map.containsKey(key)){
                    map.put(key, map.get(key)+1);
                }else{
                    //已经是两个点了，所以初次放2
                    map.put(key,2);
                }
                max = Math.max(map.get(key),max);

            }
        }
        return max;
    }

    static int gcd(int a, int b) {
        //如果纵坐标差为0，那么两个点构成的线和x轴平行。直接返回a为其逻辑斜率
        //不为
        return b == 0 ? a : gcd(b, a % b);
    }

    public static void main(String[] args) {
        int[][] ints = new int[4][2];
        ints[0] = new int[]{1,1};
        ints[1] = new int[]{2,2};
        ints[2] = new int[]{3,3};
        ints[3] = new int[]{4,4};
        System.out.println(maxPoints(ints));
    }
}
//leetcode submit region end(Prohibit modification and deletion)
